#include <stdio.h>
#include <windows.h>
#include <malloc.h>

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
#define ELEM_INITIAL 0

#define TRUE 1
#define FALSE 0

	typedef int elemType;
	typedef struct {
		elemType* base;
		elemType* top;
		int stacksize;
	} SqStack;

	//S.top point to the first position which is available.

	int _error(char* msg)
	{
		printf("%s\n",msg);
		system("pause");
		exit(FALSE);
		return 0;
	}

	int InitStack(SqStack* S)
	{
		S->base = (elemType*) malloc(sizeof elemType * STACK_INIT_SIZE);
		if (!S->base) _error("Stack init error.");

		S->top = S->base;
		S->stacksize = STACK_INIT_SIZE;

		return TRUE;
	}

	int DestroyStack(SqStack* S)
	{
		free(S->base);

		S->base = NULL;
		S->top = S->base;
		S->stacksize = 0;
		
		return TRUE;
	}

	int ClearStack(SqStack* S)
	{
		while(S->top-- != S->base)
		{
			*S->top = ELEM_INITIAL;
		}
		*S->base = ELEM_INITIAL;
		
		S->top = S->base;

		return TRUE;
	}

	int StackLength(SqStack S)
	{
		return S.top - S.base;
	}

	int StackEmpty(SqStack S)
	{
		if (!StackLength(S)) return TRUE;
		else return FALSE;
	}

	int GetTop(SqStack S, elemType* e)
	{
		if (StackEmpty(S)) return FALSE;

		*e = *--S.top;

		return TRUE;
	}

	int Push(SqStack* S, elemType e)
	{
		elemType* newBase;
		int len = StackLength(*S);

		if (len >= S->stacksize)
		{
			newBase = (elemType*) realloc(S->base, S->stacksize + STACK_INCREMENT);

			if (!newBase)
			{
				S->base = newBase;
				S->top = S->base + len;
				S->stacksize += STACK_INCREMENT;
			}
			else _error("!!Resize overflow.");
		}

		*S->top++ = e;
	
		return TRUE;
	}

	int Pop(SqStack* S,elemType* e)
	{
		if (StackEmpty(*S)) return FALSE;

		*e = *--S->top;

		return FALSE;
	}

	int _show(elemType e)
	{
		printf("value:\t%d\n",e);
		return TRUE;
	}

	int StackTraverse(SqStack S, int (*visit)(elemType) = _show)
	{
		if(StackEmpty(S)) return FALSE;

		while(--S.top != S.base)
		{
			visit(*S.top);
		}
		visit(*S.top);

		return TRUE;
	}

	int _showImg(SqStack S)
	{
		if (StackEmpty(S)) return FALSE;

		printf("|     |\n");
		while(--S.top != S.base)
		{
			printf("|%5d|\n", *S.top);
		}
		printf("|%5d|\n", *S.top);
		printf("|-----|\n");

		return TRUE;
	}

	int _showStatus(SqStack S)
	{
		printf("\nStack size:\t%d\nBase & Top:\t%X, %X\nLength:\t%d\n\n",S.stacksize, S.base, S.top, StackLength(S));
		
		if (_showImg(S)) printf("\n");
		
		return TRUE;
	}

	int main()
	{
		SqStack examS;
		elemType examE;
		int i=10;

		printf("##Stack will be initialed.\n");
		InitStack(&examS);
		_showStatus(examS);

		printf("##Push new element into stack.\n");
		while(--i) Push(&examS, i);
		_showStatus(examS);

		printf("##Destroy the stack.\n");
		DestroyStack(&examS);
		_showStatus(examS);

//		printf("##Try push new element to a bad stack.\n");
//		Push(&examS, 123);
//		_showStatus(examS);

		printf("##Initial the track again.\n");
		InitStack(&examS);
		_showStatus(examS);

		printf("##Push new element again.\n");
		while(++i != 5) Push(&examS, i);
		_showStatus(examS);

		printf("Pop existed element.\n");
		while (++i != 8)
		{
			Pop(&examS, &examE);
			printf("Value '%d' has been poped.\n", examE);
		}
		_showStatus(examS);

		DestroyStack(&examS);
		system("pause");
	}